/*
    * Copyright (C) 2013 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License");
    * you may not use this file except in compliance with the License.
    * You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.google.common.math;
  
  import com.google.caliper.BeforeExperiment;
  import com.google.caliper.Benchmark;
  import com.google.caliper.Param;
  import com.google.caliper.api.SkipThisScenarioException;
  import com.google.common.primitives.Doubles;
  
  import java.util.Random;
  
  /**
   * Benchmarks for various algorithms for computing the mean and/or variance.
   * 
   * @author Louis Wasserman
   */
  public class StatsBenchmark {
  
    enum MeanAlgorithm {
      SIMPLE {
        @Override
        double mean(double[] values) {
          double sum = 0.0;
          for (double value : values) {
            sum += value;
          }
          return sum / values.length;
        }
      },
      KAHAN {
        @Override
        double mean(double[] values) {
          double sum = 0.0;
          double c = 0.0;
          for (double value : values) {
            double y = value - c;
            double t = sum + y;
            c = (t - sum) - y;
            sum = t;
          }
          return sum / values.length;
        }
      },
      KNUTH {
        @Override
        double mean(double[] values) {
          double mean = values[0];
          for (int i = 1; i < values.length; i++) {
            mean = mean + (values[i] - mean) / (i + 1);
          }
          return mean;
        }
      };
  
      abstract double mean(double[] values);
    }
  
    static class MeanAndVariance {
      private final double mean;
      private final double variance;
  
      MeanAndVariance(double mean, double variance) {
        this.mean = mean;
        this.variance = variance;
      }
  
      @Override
      public int hashCode() {
        return Doubles.hashCode(mean) * 31 + Doubles.hashCode(variance);
      }
    }
  
    enum VarianceAlgorithm {
      DO_NOT_COMPUTE {
        @Override
        MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
          return new MeanAndVariance(meanAlgorithm.mean(values), 0.0);
        }
      },
      SIMPLE {
        @Override
        MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
          double mean = meanAlgorithm.mean(values);
          double sumOfSquaresOfDeltas = 0.0;
         for (double value : values) {
           double delta = value - mean;
           sumOfSquaresOfDeltas += delta * delta;
         }
         return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
       }
     },
     KAHAN {
       @Override
       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
         double mean = meanAlgorithm.mean(values);
         double sumOfSquaresOfDeltas = 0.0;
         double c = 0.0;
         for (double value : values) {
           double delta = value - mean;
           double deltaSquared = delta * delta;
           double y = deltaSquared - c;
           double t = sumOfSquaresOfDeltas + deltaSquared;
           c = (t - sumOfSquaresOfDeltas) - y;
           sumOfSquaresOfDeltas = t;
         }
         return new MeanAndVariance(mean, sumOfSquaresOfDeltas / values.length);
       }
     },
     KNUTH {
       @Override
       MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm) {
         if (meanAlgorithm != MeanAlgorithm.KNUTH) {
           throw new SkipThisScenarioException();
         }
         double mean = values[0];
         double s = 0.0;
         for (int i = 1; i < values.length; i++) {
           double nextMean = mean + (values[i] - mean) / (i + 1);
           s += (values[i] - mean) * (values[i] - nextMean);
           mean = nextMean;
         }
         return new MeanAndVariance(mean, s / values.length);
       }
     };
 
     abstract MeanAndVariance variance(double[] values, MeanAlgorithm meanAlgorithm);
   }
 
   @Param({"100", "10000"})
   int n;
 
   @Param
   MeanAlgorithm meanAlgorithm;
   @Param
   VarianceAlgorithm varianceAlgorithm;
 
   private double[][] values = new double[0x100][];
 
   @BeforeExperiment
   void setUp() {
     Random rng = new Random();
     for (int i = 0; i < 0x100; i++) {
       values[i] = new double[n];
       for (int j = 0; j < n; j++) {
         values[i][j] = rng.nextDouble();
       }
     }
   }
 
   @Benchmark int meanAndVariance(int reps) {
     int tmp = 0;
     for (int i = 0; i < reps; i++) {
       tmp += varianceAlgorithm.variance(values[i & 0xFF], meanAlgorithm).hashCode();
     }
     return tmp;
   }
 }